package com.njupt.Tree;



import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/28 9:20
 * @Description: 110. 平衡二叉树
 * @Version: 1.0
 */


public class IsBalanced {

    /**
     * 后续遍历递归算法
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        if(Math.abs(leftDepth-rightDepth) >=2){
            return false;
        }
        boolean left = isBalanced(root.left);
        boolean right = isBalanced(root.right);
        return left && right;
    }

    /**
     * 求二叉树的高度，递归算法后续遍历
     * @param root
     * @return
     */
    public int depth(TreeNode root){

        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        return left>right?left+1:right+1;
    }


    /**
     * 非递归算法
     * @param root
     * @return
     */
    public boolean isBalanced1(TreeNode root){

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                //处理逻辑
                int leftDepth = depth(cur.left);
                int rightDepth = depth(cur.right);
                if(Math.abs(leftDepth-rightDepth)>=2){
                    return false;
                }
                stack.push(cur);
                cur = cur.left;

            }else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return true;

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(2);
//        root.left.left = new TreeNode(3);
//        root.left.left.left = new TreeNode(4);
//        root.right.right = new TreeNode(3);
//        root.right.right.right = new TreeNode(4);


        IsBalanced test = new IsBalanced();
        System.out.println(test.isBalanced1(root));
    }
}
